package avltree;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2022/6/30
 * \* Time: 19:31
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class AVLTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public int bf;
        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;//根节点

    public boolean insert(int val){
        TreeNode node =new TreeNode(val);
        if(root == null){
            root = node;
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val){
                return false;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
        //走到这里说明cur为null
        if(parent.val < val){
            parent.right = node;
        }else{
            parent.left = node;
        }
        //
        node.parent = parent;
        cur = node;

        //调节平衡因子
        while (parent != null){
            if(cur == parent.right){
                parent.bf++;
            }else {
                parent.bf--;
            }
            if(parent.bf == 0){
                break;
            }else if(parent.bf == 1 || parent.bf == -1){
                //继续向上调节平衡因子
                cur = parent;
                parent = cur.parent;
            }else {
                if(parent.bf == 2){//说明右树高，需要降低右树高度
                    if(cur.bf == 1){
                        //左旋
                        rorateLeft(parent);
                    }else {
                        //cur.bf == -1;右旋
                        rorateRight(parent);
                    }
                }else{
                    //parent.bf == -2，说明左数高，需要降低左树的
                    if(cur.bf == -1){
                        //右旋
                        rorateRight(parent);
                    }else{
                        //cur.bf == 1

                    }
                }
                //上述代码走完就平衡了
                break;
            }
        }
        return true;
    }

    /**
     * 左单旋
     * @param parent
     */
    private void rorateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;
        if(subRL != null){
            subRL.parent = parent;
        }
        TreeNode pParent = parent.parent;

        parent.parent = subR;
        if(root == parent){
            root = subR;
            root.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.bf = parent.bf = 0;
    }

    /**
     * 右单旋
     * @param parent
     */

    private void rorateRight(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;
        if(subLR != null){
            subLR.parent = parent;
        }


        //必须先记录
        TreeNode pParent = parent.parent;
        parent.parent = subL;

        //检查当前是不是根节点
        if(parent == root){
            root = subL;
            root.parent = null;
        }else{//如果不是根节点，则判断这棵子树是在左子树还是右子树上面
            if(pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = 0;
        parent.bf = 0;


    }
}
